package jutf8search;

import java.io.Serializable;
import java.util.Vector;

/**
 * The Boyer-Moore-Horspool algorithm, imeplemented with the jutf8search.Search interface.
 * 
 */
@SuppressWarnings("serial")
public class BMH implements ExactSearchInterface, Serializable
{

    private int[]  skip; // bad character shift list
    private int    m;    // pattern size
    private byte[] query;
    private long   match;
	    
    /*
     *  Boyer-Moore-Horspool Algorithm, returns position of matchNum match
     */
    public long matchNum(byte[] text, long matchNum)
    {
        int i=0, j;
        int unsignedByte=0;
        //System.out.println(query.length+","+m+","+text.length);
        while(i <= text.length - m)
        {
            j = m-1;
            while(j>=0 && query[j] == text[i+j]) j--;
            if(j<0) 
            {
                match++;
                if(match == matchNum) return i;
                i += m;
            }
            else
            {
                unsignedByte = text[i+j] & 0xFF;
                i += skip[unsignedByte];
                //System.out.println("mismatch in text and pattern ("+j+") at text char "+unsignedByte+", pat char "+query[j]+" skip="+skip[unsignedByte]);
            }
       } 
       return -1;
    }
    
    /*
     *  Boyer-Moore-Horspool Algorithm, returns number of matches in text
     */
    public long numMatches(byte[] text)
    {
        int i=0, j, last = m -1;
        long numMatches = 0;
        int unsignedByte=0;
        while(i <= text.length - m)
        {
            j = last;
            while(j>=0 && query[j] == text[i+j]) j--; 
            // if full match
            if(j<0) 
            {
                numMatches++;
                i += m;
            }
            // otheriwise move on
            else
            {
                unsignedByte = text[i+j] & 0xFF;
                i += skip[unsignedByte];
            }
       } 
       return numMatches;
    }

    /*
     *  Boyer-Moore-Horspool Algorithm, returns all match positions in text
     */
    public Vector<Long> fullSearch(byte[] text)
    {
        int i=0, j, last = m -1;
        //int numMatches = 0;
        int unsignedByte=0;
        Vector<Long> results = new Vector<Long>();
        while(i <= text.length - m)
        {
            j = last;
            while(j>=0 && query[j] == text[i+j]) j--; 
            // if full match
            if(j<0) 
            {
                results.add(new Long(i));
                i += m;
            }
            // otheriwise move on
            else
            {
                unsignedByte = text[i+j] & 0xFF;
                i += skip[unsignedByte];
            }
       } 
       return results;
    }

    /*
     *  Build the table with a String query
     */
	public void buildTable(String query)
    {
	    buildTable(Utilities.getBytes(query));
	}

    /*
     *  Build the table with a byte[] query
     */
	public void buildTable(byte[] query)
    {
        m = query.length;
        this.query = query;
		computeBadCharShift(query);
        //printArray(skip);
	}

    /*
     *  Build table of right most occurances of each character for shifts
     */
    public void computeBadCharShift(byte[] query)
    {
        int unsignedByte = 0;
        skip = new int[ExactSearch.ALPHABET_SIZE];
        for(int i=0; i<ExactSearch.ALPHABET_SIZE; i++) 
            skip[i] = query.length;
        for(int i=0; i<query.length-1; i++)
        {
            unsignedByte = query[i] & 0xFF;
            skip[unsignedByte] = m - 1 - i;
        }
    }

	public int getPatternSize() {
		return m;
	}
    
	public void resetMatch() {
		match = 0;
	}
    
    public void printArray(int[] a)
    {
        for(int i=0; i<a.length; i++) System.out.println("["+i+"] "+a[i]);
    }
}
